package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 688. “马”在棋盘上的概率
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/5 14:50
 */
public class KnightProbability {

    public static void main(String[] args) {
        KnightProbability test = new KnightProbability();

        //输出: 0.0625
        int a = 3;
        int b = 2;
        int c = 0;
        int d = 0;

        double v = test.knightProbability(a, b, c, d);
        System.out.println(v);
    }

    public double knightProbability(int n, int k, int row, int column) {
        double[][] arr1 = new double[n][n];
        double[][] arr2 = new double[n][n];
        int[][] items = {{1, -2}, {1, 2}, {-1, -2}, {-1, 2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
        arr1[row][column] = 1;
        for (int m = 0; m < k; m++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int[] item : items) {
                        int a = i + item[0];
                        int b = j + item[1];
                        if (a < 0 || b < 0 || a >= n || b >= n) {
                            continue;
                        }
                        arr2[a][b] += arr1[i][j];
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    arr1[i][j] = arr2[i][j];
                    arr2[i][j] = 0D;
                }
            }
        }
        double sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum += arr1[i][j];
            }
        }
        return sum / Math.pow(8, k);
    }


}
